package com.putable.pqueue;


public class PQueueImpl extends DoubleAndCopy {
	/**
	 * @param qIndex The index of the array we are currently at
	 */
	private int qIndex = 1;
	
	@Override
	public void delete(PQAble p) {
		qIndex --;
		PQAble last = this.get(qIndex);
		//adds the last one to p's place
		add(last, p.getIndex());
		bubbleUp(last);
		bubbleDown(last);
		//bubbles up and down to ensure it gets to right spot
		add(null, qIndex);
	}

	@Override
	public void insert(PQAble p) {
		add(p,qIndex);
		bubbleUp(p);
		qIndex++;
	}

	@Override
	public PQAble remove() {
		//First in line
		PQAble pq = this.get(1);
		//Lower the number of pqables in queue
		qIndex--;
		//Puts the least index at the top of the queue and bubbles down
		add(this.get(qIndex), 1);
		bubbleDown(this.get(1));
		add(null, qIndex);
		return pq;
	}

	@Override
	public int size() {
		return qIndex - 1;
	}
	/**
	 * Bubbles up binary tree by comparing itself to its parent and 
	 * swapping if it is a higher value
	 * @param p The PQAble element we are bubbling up
	 */
	private void bubbleUp(PQAble p){
		PQAble parent;
		
		while(true){
			if((parent = getParent(p)) == null) break;
			if(p.compareTo(parent) > 0){
				swap(p, parent);
			}else{
				break;
			}
		}
	}
	/**
	 * Bubbles down the binary tree by comparing a parent node to its children
	 * and swapping if they are greater
	 * @param parent
	 */
	private void bubbleDown(PQAble parent){
		PQAble lChild, rChild;
		while(true){
			boolean left = true;
			if((lChild = getLeftChild(parent)) == null) break;
			if((rChild = getRightChild(parent)) != null){
				if(lChild.compareTo(rChild) < 0) left = false;
			}
			//Compare the parent with the higher priority child
			if(left == true){
				if(parent.compareTo(lChild) < 0){
					swap(lChild, parent);
				}else 
					break;
			}else{
				if(parent.compareTo(rChild) < 0){
					swap(rChild, parent);
				}else
					break;
			}
		}
	}
	/**
	 * Gets the parent of a node in the queue
	 * @param child The node to get the parent of
	 * @return The parent node
	 */
	private PQAble getParent(PQAble child){
		return this.get((child.getIndex()/2));
	}
	/**
	 * Gets the left child of a node in the queue
	 * @param parent The parent node
	 * @return The left child
	 */
	private PQAble getLeftChild(PQAble parent){
		return this.get((parent.getIndex()*2));
	}
	/**
	 * Gets the left child of a node in the queue
	 * @param parent The parent node
	 * @return The left child
	 */
	private PQAble getRightChild(PQAble parent){
		return this.get(((parent.getIndex()*2)+1));
	}
	/**
	 * Swaps p1 with p2 in the queue
	 * @param p1 PQAble that gets swapped with p2
	 * @param p2 PQAble that gets swapped with p1
	 */
	private void swap(PQAble p1, PQAble p2){
		int p1Idx = p1.getIndex();
		add(p1, p2.getIndex());
		add(p2, p1Idx);
	}
}
